package com.example.algorithm.dynamicprogramming;

import java.util.Arrays;

/**
 * 有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。
 *  每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
 *       如果 x == y，那么两块石头都会被完全粉碎；
 *       如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
 *  最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。
 * 
 *  示例 1：
 * 输入：stones = [2,7,4,1,8,1]
 * 输出：1
 * 解释：
 * 组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
 * 组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
 * 组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
 * 组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。
 *
 *  示例 2：
 * 输入：stones = [31,26,33,21,40]
 * 输出：5
 */
public class Leetcode1049_LastStoneWeightII {
    public static void main(String[] args) {
        int[] stones = {2, 7, 4, 1, 8, 1};
        stones = new int[] {31, 26, 33, 21, 40};
        System.out.println(new Solution().lastStoneWeightII(stones));
    }


    static class Solution {
        /**
         * 题目如果换种说法就简单了：stones = [2,7,4,1,8,1]，在每一个数字前添加+或-，使式子的绝对值最小。就可以转化成LeetCode494了
         * 这意味我们最终得到的结果，可以为原来 stones 数组中的数字添加 +/− 符号(即将stones分成两堆(正/负号堆))，所形成的「计算表达式」所表示。
         * 问题就被转换为：为 stones 中的每个数字添加 +/−，使得形成的「计算表达式」结果绝对值最小
         * 再进一步，假设stones的数组和为sum，假设要添-的数字的和为neg，那么最后要求（sum - neg） - neg的绝对值最小，就变成了01背包问题
         * 再进一步,由于想要「计算表达式」结果绝对值，因此我们需要将石子划分为差值最小的两个堆
         * 即是说从 stones 数组中选择，凑成总和不超过 sum // 2 的最大价值。
         *
         * 为什么可以不考虑有放回的石子呢？
         *     其实所谓的「有放回」操作，只是触发调整「某个原有石子」所在「哪个堆」中，并不会真正意义上的产生「新的石子重量」
         *     假设有起始石子 a 和 b，且两者重量关系为 a >= b，那么首先会将 a 放入「正号堆」，将 b 放入「负号堆」。
         *     重放回操作可以看作产生一个新的重量为 a−b 的“虚拟石子”，将来这个“虚拟石子”也会参与某次合并操作，也会被添加 +/− 符号：
         *         当对“虚拟石子”添加 + 符号，即可 +(a - b)，展开后为 a - b，即起始石子 a 和 b 所在「石子堆」不变
         *         当对“虚拟石子”添加 − 符号，即可 -(a - b)，展开后为 b - a，即起始石子 a 和bb 所在「石子堆」交换
         *     因此所谓不断「合并」&「重放」，本质只是在构造一个折叠的计算表达式，最终都能展开扁平化为非折叠的计算表达式。
         * @param stones
         * @return
         */
        public int lastStoneWeightII(int[] stones) {
            int totalSum = Arrays.stream(stones).sum();
            int targetMax = totalSum / 2;
            // dp[i][j] 表示是否存在 在数组 nums 的前 i 个(nums[0:i])数中选取若干元素，使得这些元素之和等于j
//            boolean[][] dp = new boolean[stones.length + 1][targetMax + 1];
//            dp[0][0] = true; // 初始值
//            // 遍历求所有可能和
//            for (int i = 1; i <= stones.length; i++) {
//                for (int j = 0; j <= targetMax; j++) {
//                    if (j < stones[i - 1])
//                        dp[i][j] = dp[i - 1][j]; // j < stones[i - 1] 则 当前值一定不可能被选
//                    else
//                        // j >= stones[i - 1] 则 当前值可能不被选，也可能被选，所以只要一个为true即为true
//                        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - stones[i - 1]];
//                }
//            }
//
//            int res = 0;
//            for (int j = targetMax; j >= 0; j--) { // 从后向前的到最小结果
//                if (dp[stones.length][j]) {
//                    res = totalSum - 2 * j;
//                    break;
//                }
//            }
//            return res;

            // 空间优化写法：由于当前状态只与上一行有关，所以可以进行空间优化(从后向前直接将上一行的值进行覆盖即可)
            boolean[] dp = new boolean[targetMax + 1];
            dp[0] = true;
            for (int i = 1; i <= stones.length; i++) {
//                for (int j = targetMax; j >= 0; j--) {
//                    if (j >= stones[i - 1])
//                        dp[j] = dp[j - stones[i - 1]] || dp[j];
//                }
                // 等价于下面写法
                for (int j = targetMax; j >= stones[i - 1]; j--) {
                        dp[j] = dp[j - stones[i - 1]] || dp[j];
                }
            }
            int res = 0;
            for (int j = targetMax; j >= 0; j--) {
                if (dp[j]) {
                    res = totalSum - 2 * j;
                    break;
                }
            }
            return res;
        }
    }
}
